|
In number theory, Zolotarev's lemma states that the Legendre symbol : for an integer ''a'' modulo an odd prime number ''p'', where ''p'' does not divide ''a'', can be computed as the sign of a permutation: : where ε denotes the signature of a permutation and π''a'' is the permutation of the nonzero residue classes mod ''p'' induced by multiplication by ''a''. For example, take ''a'' = 2 and ''p'' = 7. The nonzero squares mod 7 are 1, 2, and 4, so (2|7) = 1 and (6|7) = −1. Multiplication by 2 on the nonzero numbers mod 7 has the cycle decomposition (1,2,4)(3,6,5), so the sign of this permutation is 1, which is (2|7). Multiplication by 6 on the nonzero numbers mod 7 has cycle decomposition (1,6)(2,5)(3,4), whose sign is −1, which is (6|7). ==Proof== In general, for any finite group ''G'' of order ''n'', it is easy to determine the signature of the permutation π''g'' made by left-multiplication by the element ''g'' of ''G''. The permutation π''g'' will be even, unless there are an odd number of orbits of even size. Assuming ''n'' even, therefore, the condition for π''g'' to be an odd permutation, when ''g'' has order ''k'', is that ''n''/''k'' should be odd, or that the subgroup <''g''> generated by ''g'' should have odd index. We will apply this to the group of nonzero numbers mod ''p'', which is a cyclic group of order ''p'' − 1. The ''j''th power of a primitive root modulo p will by index calculus have index the greatest common divisor :''i'' = (''j'', ''p'' − 1). The condition for a nonzero number mod ''p'' to be an quadratic non-residue is to be an odd power of a primitive root. The lemma therefore comes down to saying that ''i'' is odd when ''j'' is odd, which is true ''a fortiori'', and ''j'' is odd when ''i'' is odd, which is true because ''p'' − 1 is even (''p'' is odd). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zolotarev's lemma」の詳細全文を読む スポンサード リンク
|